<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    120. Triangle
   </h1>
   <p>
    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
   </p>
   <p>
    For example, given the following triangle
   </p>
   <pre>
[
     [<strong>2</strong>],
    [<strong>3</strong>,4],
   [6,<strong>5</strong>,7],
  [4,<strong>1</strong>,8,3]
]
</pre>
   <p>
    The minimum path sum from top to bottom is
    <code>
     11
    </code>
    (i.e.,
    <strong>
     2
    </strong>
    +
    <strong>
     3
    </strong>
    +
    <strong>
     5
    </strong>
    +
    <strong>
     1
    </strong>
    = 11).
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <p>
    Bonus point if you are able to do this using only
    <em>
     O
    </em>
    (
    <em>
     n
    </em>
    ) extra space, where
    <em>
     n
    </em>
    is the total number of rows in the triangle.
   </p>
  </div>
  <div>
   <h1 class="question_title">
    120. 三角形最小路径和
   </h1>
   <p>
    给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
   </p>
   <p>
    例如，给定三角形：
   </p>
   <pre>[
     [<strong>2</strong>],
    [<strong>3</strong>,4],
   [6,<strong>5</strong>,7],
  [4,<strong>1</strong>,8,3]
]
</pre>
   <p>
    自顶向下的最小路径和为&nbsp;
    <code>
     11
    </code>
    （即，
    <strong>
     2&nbsp;
    </strong>
    +&nbsp;
    <strong>
     3
    </strong>
    &nbsp;+&nbsp;
    <strong>
     5&nbsp;
    </strong>
    +&nbsp;
    <strong>
     1
    </strong>
    &nbsp;= 11）。
   </p>
   <p>
    <strong>
     说明：
    </strong>
   </p>
   <p>
    如果你可以只使用
    <em>
     O
    </em>
    (
    <em>
     n
    </em>
    )&nbsp;的额外空间（
    <em>
     n
    </em>
    为三角形的总行数）来解决这个问题，那么你的算法会很加分。
   </p>
  </div>
 </body>
</html>